
// RoughHillsGenerator2.cpp

// Implements the cRoughHillsGenerator2 representing a proof-of-concept generator of rough hills, second iteration

/*
	This is the first iteration of the algorithm. It's only aimed at height generation.
For each chunk, an area of neighboring "hills" is generated, the hills being defined by series of adjacent lines with heights at each end.
Each hill is made up of a central point and "petals" that go away from it, each with a random direction and elevation differential.
Then for each block column the distance from the nearest hill line is calculated and from that the final elevation.

The hills generated look a bit better than those by RoughHillGenerator, still they need a lot of work.
Also the algorithm is quite slow, but I won't do any optimization because this is only a temporary code until we get to a better algorithm
Another iteration is expected soon.
Sometimes there are glitches in the terrain generated - one chunk in many suddenly has completely different height than its neighbors,
that is supposed to be caused by insufficient NEIGHBORHOOD_SIZE - one cHill is longer than NEIGHBORHOOD_SIZE * HILL_SIZE.
It has been found out that the distance-to-line won't work here with other than linear distance functions. If I try to make the hills rounded, they get funky. Too funky.
*/

#include "Globals.h"
#include "RoughHillsGenerator2.h"
#include "ChunkDesc.h"





#define HEIGHT_RANGE      64
#define HILL_SIZE         64
#define PETAL_SIZE        8
#define PI2               6.28318530
#define NEIGHBORHOOD_SIZE 8




class cRoughHillsGenerator2::cHill
{
	friend class cRoughHillsGenerator2;
	
public:
	cHill(cNoise & a_Noise, int a_BlockX, int a_BlockZ);
	
	void UpdateHeightMap(int a_MinX, int a_MinZ, cChunkDef::HeightMap & a_HeightMap) const;
	
protected:
	class cLine
	{
	public:
		cLine(int a_X1, int a_Y1, int a_Z1, int a_X2, int a_Y2, int a_Z2) :
			m_X1(a_X1), m_Y1(a_Y1), m_Z1(a_Z1),
			m_X2(a_X2), m_Y2(a_Y2), m_Z2(a_Z2),
			m_dX(a_X2 - a_X1), m_dY(a_Y2 - a_Y1), m_dZ(a_Z2 - a_Z1),
			m_DLen(m_dX * m_dX + m_dZ * m_dZ)
		{
		}
		
		int m_X1;
		int m_Y1;
		int m_Z1;
		int m_X2;
		int m_Y2;
		int m_Z2;
		int m_dX;    // Difference in X coords
		int m_dY;    // Difference in Y coords
		int m_dZ;    // Difference in Z coords
		int m_DLen;  // 2D length of the line (XZ), squared
		
		int GetHeightAt(int a_BlockX, int a_BlockZ) const;
	} ;
	
	typedef std::vector<cLine> cLines;
	
	cNoise m_Noise;
	cLines m_Lines;
	int m_BlockX;
	int m_BlockZ;
	
	void AddPetal(int a_BlockX, int a_BlockZ, int a_Height, double a_Direction, int a_Size);
	
	#ifdef _DEBUG
	AString ExportAsSVG(int a_Color, int a_OffsetX, int a_OffsetZ) const;
	#endif  // _DEBUG
} ;





///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// cRoughHillsGenerator2:

cRoughHillsGenerator2::cRoughHillsGenerator2(cChunkGenerator & a_ChunkGenerator) :
	super(a_ChunkGenerator),
	m_Size(HILL_SIZE),
	m_Noise(0)
{
}





cRoughHillsGenerator2::~cRoughHillsGenerator2()
{
	for (cHills::iterator itr = m_Cache.begin(), end = m_Cache.end(); itr != end; ++itr)
	{
		delete *itr;
	}
	m_Cache.clear();
}





void cRoughHillsGenerator2::Initialize(cWorld * a_World, cIniFile & a_IniFile)
{
	super::Initialize(a_World, a_IniFile);
	
	// TODO: Read the seed from INI file
	m_Noise.SetSeed(0);
}





void cRoughHillsGenerator2::GenerateBiomes(int a_ChunkX, int a_ChunkZ, cChunkDef::BiomeMap & a_BiomeMap)
{
	for (int i = 0; i < ARRAYCOUNT(a_BiomeMap); i++)
	{
		a_BiomeMap[i] = biExtremeHills;
	}
	
}





void cRoughHillsGenerator2::DoGenerate(int a_ChunkX, int a_ChunkZ, cChunkDesc &a_ChunkDesc, cEntityList & a_Entities, cBlockEntityList & a_BlockEntities)
{
	cChunkDef::BiomeMap & BiomeMap = a_ChunkDesc.GetBiomeMap();
	for (int i = 0; i < ARRAYCOUNT(BiomeMap); i++)
	{
		BiomeMap[i] = biExtremeHills;
	}

	cHills CurrentHills;
	GetHillsForChunk(a_ChunkX, a_ChunkZ, CurrentHills);
	
	cChunkDef::HeightMap & HeightMap = a_ChunkDesc.GetHeightMap();
	int MinX = a_ChunkX * cChunkDef::Width;
	int MinZ = a_ChunkZ * cChunkDef::Width;
	for (cHills::const_iterator itr = CurrentHills.begin(), end = CurrentHills.end(); itr != end; ++itr)
	{
		(*itr)->UpdateHeightMap(MinX, MinZ, HeightMap);
	}  // for itr - CurrentHills[]
	
	cChunkDef::BlockTypes & BlockTypes = a_ChunkDesc.GetBlockTypes();
	// TODO: proper terrain composition; only debugging for now:
	for (int z = 0; z < cChunkDef::Width; z++)
	{
		for (int x = 0; x < cChunkDef::Width; x++)
		{
			for (int h = cChunkDef::GetHeight(HeightMap, x, z); h >= 0; h--)
			{
				cChunkDef::SetBlock(BlockTypes, x, h, z, E_BLOCK_STONE);
			}
		}  // for x
	}  // for z
	
	// TODO
}





void cRoughHillsGenerator2::GetHillsForChunk(int a_ChunkX, int a_ChunkZ, cHills & a_Hills)
{
	int BaseX = a_ChunkX * cChunkDef::Width / m_Size;
	int BaseZ = a_ChunkZ * cChunkDef::Width / m_Size;
	if (BaseX < 0)
	{
		--BaseX;
	}
	if (BaseZ < 0)
	{
		--BaseZ;
	}
	BaseX -= NEIGHBORHOOD_SIZE / 2;
	BaseZ -= NEIGHBORHOOD_SIZE / 2;
	
	// Walk the cache, move each ravine that we want into a_Ravines:
	int StartX = BaseX * m_Size;
	int EndX = (BaseX + NEIGHBORHOOD_SIZE + 1) * m_Size;
	int StartZ = BaseZ * m_Size;
	int EndZ = (BaseZ + NEIGHBORHOOD_SIZE + 1) * m_Size;
	for (cHills::iterator itr = m_Cache.begin(), end = m_Cache.end(); itr != end;)
	{
		if (
			((*itr)->m_BlockX >= StartX) && ((*itr)->m_BlockX < EndX) &&
			((*itr)->m_BlockZ >= StartZ) && ((*itr)->m_BlockZ < EndZ)
		)
		{
			// want
			a_Hills.push_back(*itr);
			itr = m_Cache.erase(itr);
		}
		else
		{
			// don't want
			++itr;
		}
	}  // for itr - m_Cache[]
	
	for (int x = 0; x < NEIGHBORHOOD_SIZE; x++)
	{
		int RealX = (BaseX + x) * m_Size;
		for (int z = 0; z < NEIGHBORHOOD_SIZE; z++)
		{
			int RealZ = (BaseZ + z) * m_Size;
			bool Found = false;
			for (cHills::const_iterator itr = a_Hills.begin(), end = a_Hills.end(); itr != end; ++itr)
			{
				if (((*itr)->m_BlockX == RealX) && ((*itr)->m_BlockZ == RealZ))
				{
					Found = true;
					break;
				}
			}
			if (!Found)
			{
				a_Hills.push_back(new cHill(m_Noise, RealX, RealZ));
			}
		}
	}
	
	// Copy a_Hills into m_Cache to the beginning:
	cHills HillsCopy(a_Hills);
	m_Cache.splice(m_Cache.begin(), HillsCopy, HillsCopy.begin(), HillsCopy.end());
	
	// Trim the cache if it's too long:
	if (m_Cache.size() > 100 + NEIGHBORHOOD_SIZE * NEIGHBORHOOD_SIZE)
	{
		cHills::iterator itr = m_Cache.begin();
		std::advance(itr, 100 + NEIGHBORHOOD_SIZE * NEIGHBORHOOD_SIZE);
		for (cHills::iterator end = m_Cache.end(); itr != end; ++itr)
		{
			delete *itr;
		}
		itr = m_Cache.begin();
		std::advance(itr, 100 + NEIGHBORHOOD_SIZE * NEIGHBORHOOD_SIZE);
		m_Cache.erase(itr, m_Cache.end());
	}
	
	#ifdef _DEBUG
	AString fnam;
	/*
	// DEBUG: Export as SVG into a file specific for the chunk, for visual verification:
	AString SVG;
	SVG.append("<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<svg xmlns=\"http://www.w3.org/2000/svg\" width=\"1024\" height = \"1024\">\n");
	for (cHills::const_iterator itr = a_Hills.begin(), end = a_Hills.end(); itr != end; ++itr)
	{
		SVG.append((*itr)->ExportAsSVG(0, 512, 512));
	}
	SVG.append("</svg>\n");
	
	Printf(fnam, "roughhills2\\%03d_%03d.svg", a_ChunkX, a_ChunkZ);
	{
		cFile File(fnam, cFile::fmWrite);
		if (File.IsOpen())
		{
			File.Write(SVG.c_str(), SVG.size());
		}
	}
	LOGD("SVG written to %s", fnam.c_str());
	SVG.clear();
	//*/
	#endif  // _DEBUG
}





///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// cRoughHillsGenerator2::cHill:

cRoughHillsGenerator2::cHill::cHill(cNoise & a_Noise, int a_BlockX, int a_BlockZ) :
	m_Noise(a_Noise),
	m_BlockX(a_BlockX),
	m_BlockZ(a_BlockZ)
{
	m_Lines.reserve(PETAL_SIZE * 4);
	
	// Pick a direction and size:
	int Rnd = m_Noise.IntNoise2DInt(a_BlockX, a_BlockZ) / 11;
	int NumPetals = 2 + (4 / ((Rnd & 7) + 1));  // Have 2 to 6 petals, with strong preference of lower numbers
	Rnd = Rnd / 8;
	int Height = 96 + (Rnd % HEIGHT_RANGE);
	Rnd = Rnd / HEIGHT_RANGE;
	int x = a_BlockX + (Rnd % HILL_SIZE) - (HILL_SIZE / 2);
	Rnd = Rnd / HILL_SIZE;
	int z = a_BlockZ + (Rnd % HILL_SIZE) - (HILL_SIZE / 2);
	Rnd = Rnd / HILL_SIZE;
	for (int i = 0; i < NumPetals; i++)
	{
		int Rnd2 = m_Noise.IntNoise3DInt(a_BlockX, a_BlockZ, i * 17) / 19;
		double Direction = PI2 * (128 * i + (Rnd2 % 64)) / (NumPetals * 128);
		Rnd2 = Rnd2 / 64;
		AddPetal(x, z, Height, Direction, PETAL_SIZE + (Rnd2 % PETAL_SIZE));
	}
}





void cRoughHillsGenerator2::cHill::AddPetal(int a_BlockX, int a_BlockZ, int a_Height, double a_Direction, int a_Size)
{
	int Rnd = m_Noise.IntNoise3DInt(a_BlockX * 13, a_BlockZ + 19, (int)(a_Direction * 50.0) + a_Size) / 7;
	int HDif = -256;  // The slope in which the petal is "gaining" height, as a 1024-fixed-point number (1024 equals 1 block per step)
	int XDif = (int)(1024 * sin(a_Direction));
	int ZDif = (int)(1024 * cos(a_Direction));
	int MicroX = 0, MicroZ = 0, MicroH = a_Height * 1024;  // X, Y, Height as 1024-fixed-point number
	int XDif2 = 0;
	int ZDif2 = 0;
	int HDif2 = 0;
	int PrevX = a_BlockX;
	int PrevZ = a_BlockZ;
	int PrevH = a_Height;
	int NumOver = 0;
	for (int i = 0; i < a_Size;)
	{
		XDif += XDif2;
		ZDif += ZDif2;
		HDif += HDif2;
		MicroX += XDif;
		MicroZ += ZDif;
		MicroH += HDif;
		int Rnd2 = m_Noise.IntNoise3DInt(MicroX + 50, MicroZ + i, MicroH + i) / 13;
		XDif2 = 8 * ((Rnd2 % 64) - 32);
		Rnd2 = Rnd2 / 64;
		ZDif2 = 8 * ((Rnd2 % 64) - 32);
		Rnd2 = Rnd2 / 64;
		HDif2 = 96 * ((Rnd2 % 64) - 32);
		
		if (XDif > 1536)
		{
			XDif2 -= 256;
		}
		else if (XDif < -1536)
		{
			XDif2 += 256;
		}
		if (ZDif > 1536)
		{
			ZDif2 -= 256;
		}
		else if (ZDif < -1536)
		{
			ZDif2 += 256;
		}
		if (MicroH > 256 * 1024)
		{
			MicroH = 256 * 1024;
			HDif = -256;
			NumOver++;
		}
		
		int NewX = MicroX / 64;
		int NewZ = MicroZ / 64;
		m_Lines.push_back(cLine(PrevX, PrevH, PrevZ, a_BlockX + NewX, MicroH / 1024, a_BlockZ + NewZ));
		PrevX = a_BlockX + NewX;
		PrevH = MicroH / 1024;
		PrevZ = a_BlockZ + NewZ;
		i++;
	}
	// LOGD("NumOver = %d, total = %d", NumOver, a_Size);
}





void cRoughHillsGenerator2::cHill::UpdateHeightMap(int a_MinX, int a_MinZ, cChunkDef::HeightMap & a_HeightMap) const
{
	for (int x = 0; x < cChunkDef::Width; x++)
	{
		int BlockX = a_MinX + x;
		for (int z = 0; z < cChunkDef::Width; z++)
		{
			int BlockZ = a_MinZ + z;
			int CurHeight = cChunkDef::GetHeight(a_HeightMap, x, z);
			for (cLines::const_iterator itr = m_Lines.begin(), end = m_Lines.end(); itr != end; ++itr)
			{
				int PtHeight = itr->GetHeightAt(BlockX, BlockZ);
				if (CurHeight < PtHeight)
				{
					CurHeight = PtHeight;
				}
			}  // for itr - m_Points[]
			cChunkDef::SetHeight(a_HeightMap, x, z, CurHeight);
		}  // for z
	}  // for x
}





#ifdef _DEBUG
AString cRoughHillsGenerator2::cHill::ExportAsSVG(int a_Color, int a_OffsetX, int a_OffsetZ) const
{
	AString SVG;
  // Export as lines:
	for (cLines::const_iterator itr = m_Lines.begin(), end = m_Lines.end(); itr != end; ++itr)
	{
		AppendPrintf(SVG, " <path style=\"fill:none;stroke:#%06x;stroke-width:1px;\"\nd=\"M %d %d\n",
			a_Color, a_OffsetX + itr->m_X1, a_OffsetZ + itr->m_Z1
		);
		AppendPrintf(SVG, "L %d %d\" />\n", a_OffsetX + itr->m_X2, a_OffsetZ + itr->m_Z2
		);
  }
  
  // Base point highlight:
  AppendPrintf(SVG, "<path style=\"fill:none;stroke:#ff0000;stroke-width:1px;\" d=\"M %d,%d L %d,%d\"/>\n",
		a_OffsetX + m_BlockX - 5, a_OffsetZ + m_BlockZ, a_OffsetX + m_BlockX + 5, a_OffsetZ + m_BlockZ
	);
  AppendPrintf(SVG, "<path style=\"fill:none;stroke:#ff0000;stroke-width:1px;\" d=\"M %d,%d L %d,%d\"/>\n",
		a_OffsetX + m_BlockX, a_OffsetZ + m_BlockZ - 5, a_OffsetX + m_BlockX, a_OffsetZ + m_BlockZ + 5
	);

	return SVG;	
}
#endif  // _DEBUG





///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// cRoughHillsGenerator2::cHill::cLine:

int cRoughHillsGenerator2::cHill::cLine::GetHeightAt(int a_BlockX, int a_BlockZ) const
{
	// AB is this line; X is the point being queried; P is X's projection onto AB
	
	int dx = a_BlockX - m_X1;
	int dz = a_BlockZ - m_Z1;
	int Dot = m_dX * dx + m_dZ * dz;		// AX dot AB

	int Top;
	int Dist;
	if (Dot < 0)
	{
		// Nearest to first point, return height based solely on that point:
		Top = m_Y1;
		Dist = dx * dx + dz * dz;
	}
	else if ((Dot > m_DLen) || (m_DLen == 0))
	{
		// Nearest to second point, or zero length line segment, return height based solely on that point:
		Top = m_Y2;
		Dist = (m_X2 - a_BlockX) * (m_X2 - a_BlockX) + (m_Z2 - a_BlockZ) * (m_Z2 - a_BlockZ);
	}
	else
	{
		// Nearest to the line, find the projection of the point onto the line, base the height on that:
		
		// Top = m_Y1 + |AP| / |AB| * m_dY
		// |AP| / |AB| = (AB . AX) / |AB|^2
		// (AB . AX) == Dot
		// |AB|^2 == m_DLen
		Top = m_Y1 + m_dY * Dot / m_DLen;
		
		Dist = (m_dZ * dx - m_dX * dz) * (m_dZ * dx - m_dX * dz) / m_DLen;
	}
	// Version 1: simple linear distance function, works okay, but is boring:
	// return Top - (int)sqrt((double)Dist);
	
	// Version 2: make the hills rounded at top by using a square distance function. Looks weird, pretty useless:
	return Top - Dist / 96;
}




